#  Copyright (c) 2022. Lorem ipsum dolor sit amet, consectetur adipiscing elit.
#  Morbi non lorem porttitor neque feugiat blandit. Ut vitae ipsum eget quam lacinia accumsan.
#  Etiam sed turpis ac ipsum condimentum fringilla. Maecenas magna.
#  Proin dapibus sapien vel ante. Aliquam erat volutpat. Pellentesque sagittis ligula eget metus.
#  Vestibulum commodo. Ut rhoncus gravida arcu.

# !/bin/env python
# -*- coding:utf-8
"""
@author:xingz
@file:generic_search.py
@time:2022/02/18
"""
from __future__ import annotations

import heapq
from typing import *

# from future import
T = TypeVar('T')


class Stack(Generic[T]):
    def __init__(self):
        self._container: List[T] = []

    @property
    def empty(self) -> bool:
        return not self._container

    def push(self, item):
        self._container.append(item)

    def pop(self):
        return self._container.pop()

    def __repr__(self):
        return repr(self._container)


class Queue(Generic[T]):
    def __init__(self):
        self._container: Deque[T] = Deque()

    @property
    def empty(self):
        return not self._container

    def push(self, item: T):
        self._container.append(item)

    def pop(self):
        return self._container.popleft()

    def __repr__(self):
        return repr(self._container)


class PriorityQueue(Generic[T]):
    def __init__(self):
        self._container: List[T] = []

    def push(self, item):
        heapq.heappush(self._container, item)

    @property
    def empty(self):
        return not self._container

    def pop(self):
        return heapq.heappop(self._container)

    def __repr__(self):
        return repr(self._container)


class Node(Generic[T]):
    def __init__(self, state: T, parent: Optional["Node"], cost: float = 0.0, heuristic: float = 0.0):
        self.state = state
        self.parent = parent
        self.cost = cost
        self.heuristic = heuristic

    def __lt__(self, other: "Node"):
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)


def node_to_path(node: Node[T]):
    path = []
    while node.parent is not None:
        parent = node.parent
        path.append(parent.state)
        node = parent
    path.reverse()
    return path


def dfs(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T], List[T]]) -> Optional[Node[T]]:
    frontier = Stack()
    frontier.push(Node(initial, None))

    explored = {initial}
    while not frontier.empty:
        current_node = frontier.pop()
        current_state = current_node.state
        if goal_test(current_state):
            return current_node
        for child in successors(current_state):
            if child in explored:
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))


def bfs(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T], List[T]]) -> Optional[Node[T]]:
    frontier = Queue()
    frontier.push(Node(initial, None))
    explored: Set[T] = {initial}

    while not frontier.empty:
        current_node: Node[T] = frontier.pop()
        current_state: T = current_node.state
        if goal_test(current_state):
            return current_node
        for child in successors(current_state):
            if child in explored:
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))


def astar(initial: T, goal_test: Callable[[T], bool], successor: Callable[[T], List[T]], heuristic: Callable[[T], float]) -> Optional[Node[T]]:
    frontier: PriorityQueue[Node[T]] = PriorityQueue()
    frontier.push(Node(state=initial, parent=None, cost=0, heuristic=heuristic(initial)))
    explored: Dict[T, float] = {initial: 0.0}
    while not frontier.empty:
        current_node: Node[T] = frontier.pop()
        current_state = current_node.state
        if goal_test(current_state):
            return current_node
        for child in successor(current_state):
            new_cost = current_node.cost + 1
            if child not in explored or explored[child] > new_cost:
                explored[child] = new_cost
                frontier.push(Node(state=child, parent=current_node, cost=new_cost, heuristic=heuristic(child)))
    return None
